package com.atguigu.avltree;

//平衡二叉树
public class AvlTree {

    Node root;

    public static void main(String[] args) {

        //int arr[] = {1,2,3,4,5,6};

        int arr[] = {10,11,7,6,8,9};

        AvlTree avlTree = new AvlTree();

        for (int i=0;i<arr.length;i++){
            Node node = new Node(arr[i]);
            if (avlTree.root == null){
                avlTree.root = node;
            }else {
                avlTree.root.addNode(node);
            }

        }

        //avlTree.root.order();

        //树的总层数
        System.out.println(avlTree.root.cunNode());
        //左子树的总层数
        System.out.println(avlTree.root.leftCun());
        //右子树的总层数
        System.out.println(avlTree.root.rightCun());
    }

}

class Node {
    int val;
    Node leftNode;
    Node rightNode;

    //查找该树的层数
    public int cunNode(){
        return Math.max(leftNode == null?0:leftNode.cunNode(),rightNode == null?0:rightNode.cunNode())+1;
    }

    //查找左子树的层数
    public int leftCun(){
        if (leftNode == null){
            return 0;
        }
        return leftNode.cunNode();

    }

    //查找右子树的层数
    public int rightCun(){
        if (rightNode == null){
            return 0;
        }
        return rightNode.cunNode();
    }

    //左旋转，右子树层数大于左子树
    public void leftRotate(){
        //新增一个节点和root节点值一样
        Node node = new Node(val);
        //新增节点的左子节点指向原来的左子节点
        node.leftNode = this.leftNode;
        //新增节点的右子节点指向原来的右子节点的左节点
        node.rightNode = this.rightNode.leftNode;
        //将根结点的值变为右子节点的值
        this.val = rightNode.val;
        //根节点的右子节点指向原来右子节点的右节点
        this.rightNode = this.rightNode.rightNode;
        //根节点的左子节点指向原来新增的节点
        this.leftNode = node;
    }

    //右旋转
    public void rightRotate(){
        //新增一个节点和root节点值一样
        Node node = new Node(val);
        //新增节点的左子节点指向原来的左子节点
        node.rightNode = this.rightNode;
        //新增节点的右子节点指向原来的右子节点的左节点
        node.leftNode = this.leftNode.rightNode;
        //将根结点的值变为右子节点的值
        this.val = leftNode.val;
        //根节点的右子节点指向原来右子节点的右节点
        this.leftNode = this.leftNode.leftNode;
        //根节点的左子节点指向原来新增的节点
        this.rightNode = node;
    }

    //找到目标节点
    public Node findTargetNode(int val){

        if (val == this.val){
            return this;
        }

        if (val < this.val){
            if (this.leftNode != null){
                return this.leftNode.findTargetNode(val);
            }

        }

        if (val >= this.val){
            if (this.rightNode != null){
                return this.rightNode.findTargetNode(val);
            }
        }
        return null;
    }

    //找到目标节点的父节点
    public Node findParentNode(Node node){

        if (node.val < this.val){
            if (this.leftNode.val == node.val){
                return this;
            }else {
                if (this.leftNode != null){
                    return this.leftNode.findParentNode(node);
                }

            }
        }

        if (node.val > this.val){
            if (this.rightNode.val == node.val){
                return this;
            }else {
                if (this.rightNode != null){
                    return this.rightNode.findParentNode(node);
                }

            }
        }

        return null;
    }

    public void addNode(Node no){
        if (no == null){
            return;
        }

        if (no.val < this.val){
            if (this.leftNode == null){
                this.leftNode = no;
            }else {
                this.leftNode.addNode(no);
            }
        }

        if (no.val >= this.val){
            if (this.rightNode == null){
                this.rightNode = no;
            }else {
                this.rightNode.addNode(no);
            }
        }

        if (this.leftCun() - this.rightCun() > 1){
            if (leftNode != null && leftNode.rightCun() - leftNode.leftCun() > 1){
                leftNode.leftRotate();
                rightRotate();

            }else {
                rightRotate();
            }
            return;
        }

        if (this.rightCun() - this.leftCun() > 1){
            if (rightNode != null && rightNode.leftCun() - rightNode.rightCun() > 1){
                rightNode.rightRotate();
                leftRotate();

            }else {
                leftRotate();
            }
            return;
        }
    }

    //中序遍历
    public void order(){
        if (this.leftNode != null){
            this.leftNode.order();
        }

        System.out.println(this.val);

        if (this.rightNode != null){
            this.rightNode.order();
        }
    }

    public Node(int val){
        this.val = val;
    }

    public int getVal() {
        return val;
    }

    public void setVal(int val) {
        this.val = val;
    }

    public Node getLeftNode() {
        return leftNode;
    }

    public void setLeftNode(Node leftNode) {
        this.leftNode = leftNode;
    }

    public Node getRightNode() {
        return rightNode;
    }

    public void setRightNode(Node rightNode) {
        this.rightNode = rightNode;
    }

    @Override
    public String toString() {
        return "Node{" +
                "val=" + val +
                '}';
    }
}


